package org.shj.suanfa

import scala.collection.mutable.ListBuffer
import java.util.HashMap
import java.util.Stack
import java.util.function.Consumer

/**
 * 给定一个字符串列表words， 找到words 最长的word，使得这个word可用words中的其它word一次一个字符地构建(不区
 * 分大小写）。如果有多个可选答案，则返回最长的且具有最小字典序的word
 * 如： 输入  words=["a", "banana", "app", "appl", "ap", "apply", "apple"]
 *    输出： apple
 *    apple 和 apply 都可以由其它字符构建。但 apple 的字典序要小于 apply
 * 
 * 解法一： 把所有words构成一个set，查找前辍均在set中的word
 * 解法二： 因为涉及到了字符串的前辍，所以使用Trie结构（一种字符串前辍树）
 *     Trie 又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索
 *   引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。它有3个基本特质
 *     1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符
 *     2. 从根节点到某一节点，路径上经过的字符连接起来就是该节点对应的字符串
 *     3. 每个节点的所有子节点包含的字符都不相同
 *   如果某个节点为某个字符串的终结节点，则该节点上会有一个标识符。
 */
object MaxWord {
  def main(args: Array[String]): Unit = {
    
    val words = Array("a", "banana", "app", "appl", "ap", "apply", "apple")
    val trie = new Trie(words)
    trie.constructTrie()
    println(trie.dfs())
  }
}

class Trie(val words: Array[String]){
  val root = new Node('0')  
  
  def constructTrie(){
    var index = 0
    for(word <- words){
      insert(word, index)
      index += 1
    }
  }
  
  private def insert(word: String, index: Int){
    var rootNode = root
    for(c <- word){
      rootNode.next.putIfAbsent(c, new Node(c))
      rootNode = rootNode.next.get(c)      
    }
    rootNode.end = index //设置成单词在数组中的位置，可以容易地得到单词
  }
  
  def dfs(): String = {
    var rootNode: Node = null
    val stack = new Stack[Node]()
    stack.push(root)
    var max: String = null
    
    while(!stack.isEmpty()){
      rootNode = stack.pop()
      
      if(rootNode.next.keySet().isEmpty()){
        if(max == null){
          max = words(rootNode.end)
        }else{
          if(max.length() < words(rootNode.end).length()){
            max = words(rootNode.end)
          }else if(max.length() == words(rootNode.end).length()){
            if(max.compareTo(words(rootNode.end)) > 0){
              max = words(rootNode.end)
              
            }
          }          
        }
      }else{
        rootNode.next.values().toArray().foreach(item => {
          val n = item.asInstanceOf[Node]
          if(n.end > -1){
            stack.push(item.asInstanceOf[Node])
          }
        })
        
      }
    }
    
    max
  }
  
}

class Node(val c: Char){
  val next = new HashMap[Char, Node]()
  var end = -1
  
}